package com.algrithom.linktable;

import com.common.model.ListNode;

/**
 * 82. 删除排序链表中的重复元素 II
 */
public class Solution5 {
    
    public static void main(String[] args){
        Solution5 solution5 = new Solution5();
        ListNode<Integer> nodes = new ListNode<>(1);
        nodes.setNext(new ListNode<>(2));
        nodes.getNext().setNext(new ListNode<>(3));
        nodes.getNext().getNext().setNext(new ListNode<>(3));
        nodes.getNext().getNext().getNext().setNext(new ListNode<>(4));
        nodes.getNext().getNext().getNext().getNext().setNext(new ListNode<>(4));
        nodes.getNext().getNext().getNext().getNext().getNext().setNext(new ListNode<>(5));
        ListNode<Integer> result = solution5.deleteDuplicates2(nodes);
    }

    public ListNode<Integer> deleteDuplicates(ListNode<Integer> head) {
        if (head == null) {
            return head;
        }
        ListNode<Integer> dummy = new ListNode<>(0);
        ListNode<Integer> cur = dummy;
        while (cur.getNext() != null && cur.getNext().getNext() != null) {
            if (cur.getNext().getVal().equals(cur.getNext().getNext().getVal())) {
                int x = cur.getNext().getVal();
                while (cur.getNext() != null && cur.getNext().getVal() == x) {
                    cur.setNext(cur.getNext().getNext());
                }
            } else {
                cur = cur.getNext();
            }
        }

        return dummy.getNext();
    }

    public ListNode<Integer> deleteDuplicates2(ListNode<Integer> head) {
        if(head == null){
            return null;
        }
        // 找到链表头
        while(head != null && head.getNext() != null && head.getNext().getVal().equals(head.getVal())){
            while(head.getNext() != null && head.getNext().getVal().equals(head.getVal())){
                head = head.getNext();
            }
            head = head.getNext();
        }
        if(head == null){
            return head;
        }
        // 递归
        head.setNext(deleteDuplicates2(head.getNext()));
        return head;
    }
}
